/*
 * @lc app=leetcode.cn id=498 lang=javascript
 *
 * [498] 对角线遍历
 */

// @lc code=start
/**
 * @param {number[][]} mat
 * @return {number[]}
 */
//  思想：
//  分两种方式进行遍历，右上、左下
//  关键：每次遍历索引(x,y)固定，x + y = count
//  当count >= row，x保持在边界，y同理

//  复杂度：O(mn) O(mn)

var findDiagonalOrder = function (mat) {
    if (mat.length === 0) return mat
    const row = mat.length, col = mat[0].length
    let res = [], count = 0
    while (count < row + col - 1) {
        // 往右上走
        if (count % 2 === 0) {
            let x = count < row ? count : row - 1
            let y = count - x
            while (x >= 0 && y <= col - 1) {
                res.push(mat[x][y])
                x--
                y++
            }
        } else { // 往左下走
            let y = count < col ? count : col - 1
            let x = count - y
            while (y >= 0 && x <= row - 1) {
                res.push(mat[x][y])
                y--
                x++
            }
        }
        count++
    }

    return res
};
// @lc code=end

console.log(findDiagonalOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))